package 每日一题;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-16
 **/

public class No282给表达式添加运算符 {

    /**
     * 给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，
     * 在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。
     *
     * 示例 1:
     * 输入: num = "123", target = 6
     * 输出: ["1+2+3", "1*2*3"]
     * 示例 2:
     * 输入: num = "232", target = 8
     * 输出: ["2*3+2", "2+3*2"]
     * 示例 3:
     * 输入: num = "105", target = 5
     * 输出: ["1*0+5","10-5"]
     * 示例 4:
     * 输入: num = "00", target = 0
     * 输出: ["0+0", "0-0", "0*0"]
     * 示例 5:
     * 输入: num = "3456237490", target = 9191
     * 输出: []
     *
     * 提示：
     * 1 <= num.length <= 10
     * num 仅含数字
     * -231 <= target <= 231 - 1
     */

    private List<String> result = new ArrayList<>();
    private int target;
    private int[] arr;

    // 1 <= num.length <= 10
    public List<String> addOperators(String num, int target) {

        this.target = target;
        this.arr = new int[num.length()];
        // + - * 三种符号即可, 并且不是相隔每个字符,可以相隔多个字符。
        for (int i = 0; i < num.length(); i++) {
            arr[i] = num.charAt(i) - '0';
        }
        dfs(0, 0, 0, new StringBuilder());
        return result;
    }

    /**
     * 记录上一个item数,方便下次 * 运算
     * @param pre 上一个数
     * @param sum 下位和
     */
    private void dfs(int index,long pre, long sum, StringBuilder path) {

        if (index == arr.length) {
            if (sum == target) {
                result.add(path.toString());
                return;
            }
        }

        for (int i = index; i < arr.length; i++) {
            long num = getNumByArrRange(arr, index, i);
            // 1*05这种可以接受吗?不可以接受,因为不能缺字符 && 多个前导0,比如 00也要
            if (arr[index] == 0 && i - index > 0) {
                break;
            }
            if (index == 0) {
                int length = path.length();
                path.append(num);
                dfs(i + 1, num, num, path);
                path.setLength(length);
            } else {
                int length  = path.length();
                System.out.println(path);
                path.append("+").append(num);
                dfs(i + 1, num, sum + num, path);
                System.out.println(path);
                path.setLength(length);
                path.append("-").append(num);
                dfs(i + 1, -num, sum - num, path);
                System.out.println(path);
                path.setLength(length);
                path.append("*").append(num);
                dfs(i + 1,  pre * num, sum - pre + (pre * num), path);
                System.out.println(path);
                path.setLength(length);
            }

        }

    }

    private long getNumByArrRange(int[] arr, int left, int right) {
        long num = arr[left++];
        while (left <= right) {
            num *= 10;
            num += arr[left++];
        }
        return num;
    }

    public static void main(String[] args) {
        System.out.println((int)9999800001L);
        No282给表达式添加运算符 n = new No282给表达式添加运算符();
        List<String> result = n.addOperators("9999999999", 1409865409);
        System.out.println(result);
    }

}
